struct QueueNode
{
    int depth;
    struct TreeNode *data;
};
struct Queue
{
    int head;
    int tail;
    struct QueueNode **array;
};
struct Queue* init()
{
    struct Queue * queue=(struct Queue*)malloc(sizeof(struct Queue));
    queue->head=0;
    queue->tail=0;
    queue->array=(struct QueueNode**)malloc(sizeof(struct QueueNode*)*2001);
    memset(queue->array,0,sizeof(struct QueueNode*)*2001);
    return queue;
}
struct QueueNode* out(struct Queue *queue)
{
    if(queue->head==queue->tail)
    {
        return NULL;
    }
    return (queue->array)[(queue->head)++];
}
void insert(struct Queue *queue,struct QueueNode *node)
{   
    (queue->array)[(queue->tail)++]=node;
}
void myFree(struct Queue *queue)
{
    for(int i=0;i<2001;i++)
    {   
        if((queue->array)[i])
        {
            free((queue->array)[i]->data);
        }
    }
    free(queue->array);
    free(queue);
}
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    *returnSize=0;
    *returnColumnSizes=NULL;
    if(!root)
    {
        return NULL;
    }
    int **res=NULL;
    struct Queue *queue=init();
    struct QueueNode *temp=(struct QueueNode*)malloc(sizeof(struct QueueNode));
    temp->data=root;
    temp->depth=0;
    (queue->tail)++;
    (queue->array)[0]=temp;
    while(queue->head!=queue->tail)
    {    
        if( (queue->array)[queue->head] && (queue->array)[queue->head]->data)
        {
            if( (queue->array)[queue->head]->data->left)
            {
                struct QueueNode *temp=(struct QueueNode*)malloc(sizeof(struct QueueNode));
                temp->depth=(queue->array)[queue->head]->depth+1;
                temp->data=(queue->array)[queue->head]->data->left;
                insert(queue, temp);  
            }
            if( (queue->array)[queue->head]->data->right)
            {
                struct QueueNode *temp=(struct QueueNode*)malloc(sizeof(struct QueueNode));
                temp->depth=(queue->array)[queue->head]->depth+1;
                temp->data=(queue->array)[queue->head]->data->right;
                insert(queue, temp);
            }
             out(queue);
        }
       
    }
    if((queue->array)[queue->tail-1])
    {
        *returnSize=(queue->array)[queue->tail-1]->depth+1;
    }
    *returnColumnSizes=(int*)malloc(sizeof(int)* *returnSize);
    res=(int**)malloc(sizeof(int*) * *returnSize);
    int number=0;
    for(int i=0;i<queue->tail;i=i+number)
    {
        number=0; 
        for(int j=i;j<queue->tail&&(queue->array)[j]&&(queue->array)[i]&&((queue->array)[j]->depth==(queue->array)[i]->depth);j++)
        {
            number++;
        }
        if(number>0)
        {
            (*returnColumnSizes)[(queue->array)[i]->depth]=number;
            res[(queue->array)[i]->depth]=(int*)malloc(sizeof(int)*number);
            for(int j=0;j<number;j++)
            {
                res[(queue->array)[i]->depth][j]=(queue->array)[i+j]->data->val;
            }
        }
    }
    myFree(queue);
    return res;
}